/*
 * @lc app=leetcode.cn id=138 lang=cpp
 *
 * [138] 复制带随机指针的链表
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    Node *copyRandomList(Node *head)
    {
        if (!head)
            return head;
        map<Node *, int> m2i;
        vector<Node *> vec;
        Node *p = head;
        while (p)
        {
            m2i[p] = vec.size();
            Node *new_p = new Node(p->val);
            vec.push_back(new_p);
            p = p->next;
        }

        p = head;
        int i = 0;
        while (p)
        {
            if (i < vec.size() - 1)
                vec[i]->next = vec[i + 1];

            if (p->random)
            {
                vec[i]->random = vec[m2i[p->random]];
            }
            ++i;
            p = p->next;
        }

        return vec[0];
    }
};

// @lc code=end
